Minimum swaps to make strings equal

Time: O(N); Space: O(1); easy

You are given two strings s1 and s2 of equal length consisting of letters “x” and “y” only.

Your task is to make these two strings equal to each other.

You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = “xx”, s2 = “yy”

Output: 1

Explanation:

  • Swap s1[0] and s2[1], s1 = “yx”, s2 = “yx”.

Example 2:

Input: s1 = “xy”, s2 = “yx”

Output: 2

Explanation:

  • Swap s1[0] and s2[0], s1 = “yy”, s2 = “xx”.

  • Swap s1[0] and s2[1], s1 = “xy”, s2 = “xy”.

  • Note that you can’t swap s1[0] and s1[1] to make s1 equal to “yx”, cause we can only swap chars in different strings.

Example 3:

Input: s1 = “xx”, s2 = “xy”

Output: -1

Example 4:

Input: s1 = “xxyyxyxyxx”, s2 = “xyyxyxxxyx”

Output: 4

Constraints:

  • 1 <= len(s1), len(s2) <= 1000

  • s1, s2 only contain ‘x’ or ‘y’

Hints:

  1. First, ignore all the already matched positions, they don’t affect the answer at all. For the unmatched positions, there are three basic cases (already given in the examples):

  2. (“xx”, “yy”) => 1 swap, (“xy”, “yx”) => 2 swaps

  3. So the strategy is, apply case 1 as much as possible, then apply case 2 if the last two unmatched are in this case, or fall into impossible if only one pair of unmatched left. This can be done via a simple math.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def minimumSwap(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        x1, y1 = 0, 0
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                continue
            x1 += int(s1[i] == 'x')
            y1 += int(s1[i] == 'y')

        if x1%2 != y1%2:            # impossible
            return -1

        # case1: per xx or yy needs one swap, (x1//2 + y1//2)
        # case2: per xy or yx needs two swaps, (x1%2 + y1%2)
        return (x1//2 + y1//2) + (x1%2 + y1%2)

[2]:

s = Solution1()
s1 = 'xx'
s2 = 'yy'
assert s.minimumSwap(s1, s2) == 1
s1 = 'xy'
s2 = 'yx'
assert s.minimumSwap(s1, s2) == 2
s1 = 'xx'
s2 = 'xy'
assert s.minimumSwap(s1, s2) == -1
s1 = "xxyyxyxyxx"
s2 = "xyyxyxxxyx"
assert s.minimumSwap(s1, s2) == 4